import org.omg.CORBA.PUBLIC_MEMBER;

import java.util.*;

public class BinaryTree {
    /**
     * 内部类，树节点
     */
    public static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode createBinaryTree(){
        TreeNode A=new TreeNode('A');
        TreeNode B=new TreeNode('B');
        TreeNode C=new TreeNode('C');
        TreeNode D=new TreeNode('D');
        TreeNode E=new TreeNode('E');
        TreeNode F=new TreeNode('F');
        TreeNode G=new TreeNode('G');
        TreeNode H=new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;
        return A;
    }

    /**
     * 平衡树O(n平方)
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root==null)return true;
        if(Math.abs(getHeight(root.left)-getHeight(root.right))<=1
        &&isBalanced(root.left)&&isBalanced(root.right)){
            return true;
        }
        return false;
    }

    /**
     * 获取树的深度
     * @param root
     * @return
     */
    public int getHeight(TreeNode root){
        if(root==null)return 0;
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }

    /**
     * 反转二叉树
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if(root==null) return null;
        TreeNode cur=root.left;
        root.left=root.right;
        root.right=cur;
        invertTree(root.left);
        invertTree(root.right);
        return root;

    }

    /**
     * 前序遍历
     * @param root
     */
    public void priOrder(TreeNode root){
        if(root==null)return;
        System.out.print(root.val+" ");
        priOrder(root.left);
        priOrder(root.right);
    }

    /**
     * 中序遍历
     * @param root
     */
    public void inOrder(TreeNode root){
        if(root==null)return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    /**后序遍历
     *
     * @param root
     */
    public void postOrder(TreeNode root){
        if(root==null)return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    /**
     * 获取树的节点个数，遍历法
     */
    public int nodeSize;
    public void getNodeSize(TreeNode root){
        if(root==null)return;
        nodeSize++;
        getNodeSize(root.left);
        getNodeSize(root.right);
    }

    /**
     * 获取树的节点个数，递归法
     * @param root
     * @return
     */
    public int getNodeSize2(TreeNode root){
        if(root==null)return 0;
        return getNodeSize2(root.left)+getNodeSize2(root.right)+1;
    }

    /**
     * 获取树的叶子节点个数
     * @param root
     * @return
     */
    public int getLeafNodeCount(TreeNode root){
        if(root==null)return 0;
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

    /**
     * 获取第k层的节点个数
     * @param root
     * @param k
     * @return
     */
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null)return 0;
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
    }

    /**
     * 查找有无数值为val的节点
     * @param root
     * @param val
     * @return
     */
    public TreeNode find(TreeNode root, int val){
        if(root==null)return null;
        if(root.val==val){
            return root;
        }
        find(root.left,val);
        find(root.right,val);
        return null;
    }

    /**
     * 判断两颗树是否相同
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null)return true;
        //结构是否相同
        if((p!=null&&q==null)||(p==null&&q!=null)){
            return false;
        }
        //数据是否相同以及左右子树是否相同
        return p.val==q.val&&
        isSameTree(p.left,q.left)&&
        isSameTree(p.right,q.right);
    }

    /**
     * 判断一棵树是不是另一颗树的子树
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
      if(isSameTree(root,subRoot))return true;
      if(isSubtree(root.left,subRoot))return true;
      if(isSubtree(root.right,subRoot))return true;
      return false;
    }

    /**
     *对称树
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if(root==null)return true;
        return isSymmetric(root.left,root.right);
    }
    public boolean isSymmetric(TreeNode leftRoot,TreeNode rightRoot) {
        if((leftRoot==null&&rightRoot!=null)||(leftRoot!=null&&rightRoot==null)){
            return false;
        }
        if(leftRoot==null&&rightRoot==null){
            return true;
        }
        if(leftRoot.val==rightRoot.val
        &&isSymmetric(leftRoot.left,rightRoot.right)
        &&isSymmetric(leftRoot.right,rightRoot.left)){
            return true;
        }else{
            return false;
        }
    }

    /**
     * 最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return null;
        if(root==p||root==q)return root;
        TreeNode leftTree=lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree=lowestCommonAncestor(root.right,p,q);
        if(leftTree!=null&&rightTree!=null){
            return root;
        }else if(leftTree!=null&&rightTree==null){
            return leftTree;
        }else{
            return rightTree;
        }
    }
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
        Stack<TreeNode> stackp=new Stack<>();
        Stack<TreeNode> stackq=new Stack<>();
        getPath(root,p,stackp);
        getPath(root,q,stackq);
        int sizeP=stackp.size();
        int sizeQ=stackq.size();
        if(sizeP>sizeQ){
            int size=sizeP-sizeQ;
            while(size!=0){
                stackp.pop();
                size--;
            }
        }else{
            int size=sizeQ-sizeP;
            while(size!=0){
                stackq.pop();
                size--;
            }
        }
        while(!stackp.isEmpty()&&!stackq.isEmpty()){
            TreeNode node1=stackp.pop();
            TreeNode node2=stackq.pop();
            if(node1==node2){
                return node1;
            }
        }
        return null;
    }
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if(root==null)return false;
        stack.push(root);
        if(root==node)return true;
        boolean flg=getPath(root.left,node,stack);
        if(flg){
            return true;
        }
        flg=getPath(root.right,node,stack);
        if(flg){
            return true;
        }
        stack.pop();
        return false;
    }

    /**
     * 层序遍历
     * @param root
     */
    void levelOrder(TreeNode root){
        if(root==null)return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            while(size!=0){
                TreeNode cur=queue.poll();
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
                System.out.print(cur.val+" ");
                size--;
            }
            System.out.println();
        }

    }
}
